package recursive.generateTrees;

import java.util.LinkedList;
import java.util.List;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/04/02
 * @author 王光浩
 * @Thinking 使用递归实现。
 */
public class MyMethodOne {
	public List<TreeNode> generateTrees(int n) {
		return helper(1,n);
    }
	/**
	 * 将所有 在left~right范围内，分别以left到right为root的所有二叉搜索树加入到List<TreeNode>
	 * @param n
	 * @param level
	 */
	private List<TreeNode> helper(int left,int right) {
		List<TreeNode> ret=new LinkedList<TreeNode>();
		if(left>right)ret.add(null);
		else if(left==right)ret.add(new TreeNode(left));
		else {
			for(int i=left;i<=right;i++) {
				List<TreeNode> leftList=helper(left,i-1);
				List<TreeNode> rightList=helper(i+1,right);
				for(TreeNode temLeft:leftList) {
					for(TreeNode temRight:rightList) {
						TreeNode root=new TreeNode(i);
						root.left=temLeft;
						root.right=temRight;
						ret.add(root);
					}
				}
				
			}
		}
		return ret;
	}
}
